package com.faiz.algorithm;

import java.util.Arrays;

public class ArrayPartition {

    public boolean canPartition(int[] nums) {
        // 思路：转化为0-1背包问题
        int sum = Arrays.stream(nums).sum();

        if (sum % 2 == 0) {
            // 设置背包的初始重量
            int w = sum / 2;
            int len = nums.length;
            int[][] dp = new int[len + 1][w + 1];
            for (int j = 1; j <= w; j++) {
                for (int i = 1; i <= len; i++) {
                    if (j >= nums[i - 1]) {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i - 1]] + nums[i - 1]);
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
            return dp[len][w] == w;
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        ArrayPartition arrayPartition = new ArrayPartition();
        System.out.println(arrayPartition.canPartition(nums));
    }
}
